/**
 * @file
 * Expansion graph instance isomorphism.
 */
#ifndef INSTANCE_ISOMORPHISM_H
#define INSTANCE_ISOMORPHISM_H

#include <set>
#include <algorithm>

#include "expansion_graph_instance.h"
#include "expansion_graph_instance_ops.h"
#include "pairings.h"

/**
 * Identity equivalence functor for expansion graph instances.
 */
template<class V, class E>
  class ExpansionGraphInstanceIdentityEquivalence
{
 public:
  /**
   * Identity equivalence functor for expansion graph instances.
   * @param[in] i1 The first instance.
   * @param[in] i2 The other instance.
   * @return @c true if the instances are identical.
   */
  bool operator()(ExpansionGraphInstance<V,E> *i1, ExpansionGraphInstance<V,E> *i2)
  {
    std::set<E*> *edges1, *edges2;
    i1->get_edges(&edges1);
    i2->get_edges(&edges2);
    return (*edges1 == *edges2);
  }
};

/**
 * Semantic equivalence functor for expansion graph instances.
   * @param[in] i1 The first instance.
   * @param[in] i2 The other instance.
   * @return @c true if the instances are isomorphic.
 */
template<class V, class E>
  class ExpansionGraphInstanceSemanticEquivalence
{
 public:
  /**
   * 
   */
  bool operator()(ExpansionGraphInstance<V,E> *i1, ExpansionGraphInstance<V,E> *i2)
  {
      return instance_isomorphism(i1,i2);
  }
};



template<class V, class E>
  class ExpansionGraphInstanceUniqueExpansion
{
 public:
  /**
   * 
   */
  bool operator()(ExpansionGraphInstance<V,E> *i,
                  std::list<ExpansionGraphInstance<V, E> *> *result)
  {
    i->unique_expand(&occured, result);
  }
 private:
  std::set<std::set< E*> > occured;
};


template<class V, class E>
  class ExpansionGraphInstanceExpansion
{
 public:
  /**
   * 
   */
  bool operator()(ExpansionGraphInstance<V,E> *i,
                  std::list<ExpansionGraphInstance<V, E> *> *result)
  {
    i->expand(result);
  }
};

/**
 * Expansion graph instance isomorphism.
 * @param[in] i1 The first instance.
 * @param[in] i2 The other instance.
 * @result @c true if the instances are isomorphic, @c false otherwise.
 */
template<class V, class E>
  bool instance_isomorphism(ExpansionGraphInstance<V, E> *i1, 
                            ExpansionGraphInstance<V, E> *i2)
{
  // Get all possible mappings
  std::multimap<V*, V*> possible_mappings;
  
  if(! get_instance_vertex_mapping(i1, i2, &possible_mappings) )  return false;
 
  // Initialize the Pairings with all possible mappings
  Pairings<V> possible_seperated_mappings;
  for(typename std::multimap<V*, V*>::iterator i = possible_mappings.begin();
      i != possible_mappings.end();
      i++)
    possible_seperated_mappings.add_pair(i->first, i->second);
  
  // Iterate over each seperated mapping
  std::map<V*, V*> curr_possible_seperated_mapping;
  while(possible_seperated_mappings.get_next_map(&curr_possible_seperated_mapping))
    {
      // Check if constraints are satisfied
      if (check_instance_mapping(i1, i2, &curr_possible_seperated_mapping))
        // Constraints were satisfied by the current possible seperated mapping
        return true;
      else
        // Delete the current possible seperated mapping
        curr_possible_seperated_mapping.erase(curr_possible_seperated_mapping.begin(),
                                              curr_possible_seperated_mapping.end());
    }
  // No seperated mapping satisfied constraints
  return false;
}

#endif // INSTANCE_ISOMORPHISM_H
